package com.atguigu.union;


public class UnionFind5 implements UF{
    private int[]parent;
    private int[]rank;//sz[i]表示根节点为i的树的高度

    public UnionFind5(int size){
        parent=new int[size];
        rank=new int[size];
        for (int i = 0; i < size; i++) {
            parent[i]=i;
            rank[i]=1;
        }
    }
    //查找过程，查找元素p对应的集合编号
    //O(h)复杂度，h为树的高度
    private int find(int p){
        if(p<0||p> parent.length){
            throw new IllegalArgumentException("p is out od bound");
        }
        while(parent[p]!=p){
            parent[p]=parent[parent[p]];
            p=parent[p];
        }
        return p;
    }
    @Override
    public int getSize() {
        return parent.length;
    }
    //查看元素p和元素q是否属于同一个集合
    //O(h)复杂度，h为树的高度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p)==find(q);
    }
    //合并元素p和元素q所属的集合
    //O(h)复杂度，h为树的高度
    //让集合树的深度减小，让查询的效率更高效
    @Override
    public void unionElements(int p, int q) {
        int pRoot=find(p);
        int qRoot=find(q);
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上。
        if(rank[pRoot]<rank[qRoot]){
            parent[pRoot]=qRoot;
        }else if(rank[pRoot]==rank[qRoot]){
            parent[qRoot]=pRoot;
            rank[pRoot]+=1;
        }else{//rank[qRoot]<rank[pRoot]
            parent[qRoot]=pRoot;
        }
    }
}
